Section: Research Program

Lattice-based cryptography

Lattice-based cryptography (LBC) is an utterly promising, attractive (and competitive) research ground in cryptography, thanks to a combination of unmatched properties:

• Improved performance. LBC primitives have low asymptotic costs, but remain cumbersome in practice (e.g., for parameters achieving security against computations of up to 2100 bit operations). To address this limitation, a whole branch of LBC has evolved where security relies on the restriction of lattice problems to a family of more structured lattices called ideal lattices. Primitives based on such lattices can have quasi-optimal costs (i.e., quasi-constant amortized complexities), outperforming all contemporary primitives. This asymptotic performance sometimes translates into practice, as exemplified by NTRUEncrypt.

• Improved security. First, lattice problems seem to remain hard even for quantum computers. Moreover, the security of most of LBC holds under the assumption that standard lattice problems are hard in the worst case. Oppositely, contemporary cryptography assumes that specific problems are hard with high probability, for some precise input distributions. Many of these problems were artificially introduced for serving as a security foundation of new primitives.

• Improved flexibility. The master primitives (encryption, signature) can all be realized based on worst-case (ideal) lattice assumptions. More evolved primitives such as ID-based encryption (where the public key of a recipient can be publicly derived from its identity) and group signatures, that were the playing-ground of pairing-based cryptography (a subfield of elliptic curve cryptography), can also be realized in the LBC framework, although less efficiently and with restricted security properties. More intriguingly, lattices have enabled long-wished-for primitives. The most notable example is homomorphic encryption, enabling computations on encrypted data. It is the appropriate tool to securely outsource computations, and will help overcome the privacy concerns that are slowing down the rise of the cloud.

We wish to address three issues, described below.

Design of versatile cryptosystems

We will design standard and important cryptographic primitives in the LBC framework, in particular primitives that can be realized with the integer factorization problem, with the discrete logarithm problem over generic groups, and with the discrete logarithm problem over elliptic curves with pairings. This is a first step towards the longer-term goal of showing the superiority of the LBC framework in terms of possible functionalities.

We will first consider group signatures, that enable a member of a group to anonymously sign a document in the name of the group, while allowing a group authority to remove the anonymity and to trace the signer from the signature.

Another primitive we will consider is traitor tracing, a type of broadcast encryption where unauthorized decryption boxes can be used to trace the keys that were used to build them. Traitor tracing is sometimes viewed as the encryption counterpart of group signature. The objective here will be to improve the sole LBC traitor tracing scheme to efficiently achieve full traceability (where all users can collude to build a pirate decryption box), as can be achieved with pairings.

Additionally, we will consider functional encryption, which enables the decryption of ciphertexts by a set of users who share some specific attributes. This sophisticated protocol is hard to design if one needs the scheme to be secure in the strongest sense, or the description of the attributes to be very expressive, while maintaining efficiency.

Security foundations of LBC

We wish to strengthen the security foundations of LBC. This will be achieved by unifying the diverse hardness assumptions and showing that the LBC hardness assumptions are weaker than the Integer Factorization and Discrete Logarithm problems.

Most LBC primitives rely on the worst-case hardness of standard and well-studied problems on lattices. The primitives are typically constructed via Ajtai's Short Integer Solution problem (SIS) and Regev's Learning With Errors problem (LWE), to which standard lattice problems reduce. SIS and LWE are more fitted to devise cryptosystems, as they are average-case in nature. However, other primitives, and in particular the most efficient ones, rely on less accepted hardness assumptions than SIS and LWE (and thus worst-case hardness assumptions on standard lattice problems).

The LBC primitives based on the variant problems Ring-SIS/Ring-LWE, and thus lattice problems restricted to ideal lattices, are drastically more efficient than those based on SIS/LWE. It is therefore a central objective to prove that these problems are hard. Another assumption commonly used is the hardness of the Approx-GCD problem. This problem consists in finding $p$ from many samples $a_i·p+b_i$ with small random $a_i$ and $b_i$. It is not known to be harder than any standard lattice problem but is used as a security foundation anyway. It is an attractive open problem to prove its difficulty, for example by reducing standard problems over lattices to it. Achieving the above goals will unify the hardness assumptions underlying the security of LBC. We will also investigate alternatives to the well-accepted LWE/SIS approach.

The rise of efficient lattice-based cryptography

Increasing the efficiency of LBC requires algorithmic and implementation research efforts. The efficient cryptographic primitives rely on ideal lattices. These correspond, via the coordinates-coefficients mapping, to ideals of polynomial rings $Z\left[x\right]/\left(P\right)$, where $P$ is a large degree irreducible polynomial, such as $x^n+1$ with $n$ a power of 2. They may also be defined as the ideals of the rings of integers of large-degree number fields (in the case of cyclotomic number fields, these definitions are equivalent). The cryptographic primitives relying on ideal lattices typically involve two types of tasks: multiplications and additions of polynomials in the ring $(Z/pZ)\left[x\right]/\left(P\right)$, where $p$ is a medium-size integer (e.g., of 10 to 60 bits), and sampling from discrete Gaussian distributions (the integer counterpart of the normal law). We will optimize their algorithms and implementations. The objective is to obtain efficient software and hardware implementations of basic LBC primitives such as digital signatures and encryption.

Polynomial arithmetic is well known and has been well studied in computer algebra, but has not been optimized over rings $Z/pZ$ where $p$ has medium bit-size: so far, either very large (hundreds of bits) or very small (2 and 3) moduli have been considered. We will optimize the existing algorithms for this new range of parameters, for both software and hardware. Sampling from the (continuous) Gaussian distribution is also a well-studied topic. However, in LBC, we are mostly interested in the discrete Gaussian distribution, where the probability of obtaining the integer $x$ is proportional to $exp(-\pi ·x^2/s^2)$, for any $x$. All known algorithms for this task are very slow.